package com.lun.medium;

public class HouseRobberII {
	
    public int rob(int[] nums) {
        if(nums.length == 0)
        	return 0;
        
        if(nums.length == 1)
        	return nums[0];
    	
    	int first = rob(nums, 0, nums.length - 2);
    	int second = rob(nums, 1, nums.length - 1);
    	
    	return Math.max(first, second);
    }
    
    
    private int rob(int[] nums, int start, int end) {
    	int[] dp = new int[2];
    	
    	dp[0] = nums[start];
    	
    	if(start < end) {
    		dp[1] = Math.max(nums[start], nums[start + 1]);
    	}
    	
    	for(int i = start + 2; i <= end; i++) {
    		int j = i - start;//j初始为2，&1后 dp[0]，dp[1]，dp[0],...排位
    		dp[j & 1] = Math.max(dp[(j - 2) & 1] + nums[i], dp[(j - 1) & 1]);
    	}
    	
    	return dp[(end - start) & 1];//与for循环内排位同理
    }
    
}
